1. Field of the Invention
The invention concerns an asynchronous switching node distributing cells dynamically to outputs constituting an irregular group. A switching node of this kind can be used in an asynchronous telecommunication system including at least two switching nodes connected by a group of at least two transmission links. Each switching node includes an asynchronous switching network having inputs and outputs and made up of a plurality of switching elements disposed in a plurality of stages between the inputs and the outputs.
2. Description of the Prior Art
It is desirable to transfer cells from one node to the other by distributing them regularly to the various transmission links constituting a group, a link being selected cell by cell so that all links receive as close to the same number of cells as possible, in the short term, assuming that the links have the same maximum bit rate.
This prior art method has advantages: improved efficiency of the links between the nodes and improved reliability of communications on the available links in the group. However, it raises the following problem: for each cell the node must be able to identify a group of outputs of the node connected to the group of transmission links to which the cell is addressed; it must then select dynamically one of the outputs thus identified whilst achieving a statistically balanced distribution to the output ports of each group, to which the cell is transferred.
A distinction must be drawn between two situations:
either each group of outputs is regular, i.e. made up of outputs whose addresses are mathematically related; PA1 or some groups are irregular, i.e. made up of outputs whose addresses are not mathematically related. PA1 a first time to transfer the cell from first inputs to first outputs of the node, a regular group of links connecting the first outputs of a node to a distributor device distributing the cells at random to the links and then returning them to second inputs of the same node; and PA1 a second time to transfer the cell from the second inputs to second outputs of the node in order to send the cell on a link of the irregular group of links which constitutes the destination of the cell. PA1 an input stage receiving cells on a plurality of inputs and receiving for each cell external routing information, said first stage adding to each cell an internal routing label conditioned by said external routing data; and PA1 a plurality of switching stages each including at least one switching element each including means for transferring a cell received at one of its inputs to at least one of its outputs according to said internal routing label associated with said cell; PA1 in which node said input stage includes means for selecting, for each cell addressed to an irregular group of outputs, a routing label from predetermined internal routing labels respectively identifying regular subgroups of outputs, the combination of which constitutes said irregular group, each regular subgroup including a single output or a plurality of outputs whose addresses are mathematically related. PA1 means for identifying a group of outputs (routing group) of the outputs of said element providing access via different paths to one of the outputs of a regular subgroup identified by the internal routing label, and PA1 means for selecting any output from the identified group of outputs, at least one of a predetermined internal routing labels identifying a regular subgroup including a plurality of outputs. PA1 means for identifying at least one output from each group of outputs of said element, identified by a distribution tree number in the internal routing label of said cell, and PA1 means for outputting a copy of said cell on each of the outputs thus selected, at least one of the predetermined internal routing labels identifying a broadcast tree for routing one copy of a cell to a regular subgroup of each of the irregular groups constituting the destinations of that cell.
For example, the addresses of outputs constituting a regular group are in the form: ABXDEFXXIJXX, where A, B, D, E, F, I, J are fixed binary values defining the address of the group and X is a symbol representing either binary value. This address identifies a regular group of 32 outputs with the respective following addresses:
______________________________________ ABODEFOOIJOO ABODEFOOIJO1 ABODEFOOIJ1O ABODEFOOIJ11 ABODEFO1IJOO ABODEFO1IJO1 ABODEFO1IJ1O ABODEFO1IJ11 ABODEF1OIJOO ABODEF10IJO1 ABODEF1OIJ1O ABODEF1OIJ11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . AB1DEF11IJ11 ______________________________________
In the above example, the four possible values of the last pair of bits XX correspond to subgroups each made up of four consecutive outputs and the other three X bits replicate these subgroups of four outputs eight times over, with a regular distribution within the overall set of output addresses.
European patent application n.degree. 91-201915.5 filed 22 Jul. 1991 describes a node capable of distributing cells dynamically to outputs constituting a regular group. The node essentially comprises a switching network which includes a plurality of stages each constituted by at least one switching element. The outputs of the switching network are grouped into a plurality of regular groups, each group comprising at least one output.
The switching network used is of the multipath self-routing type: the path followed by a cell addressed to a given output is not entirely decided when it enters the network, but rather step by step in each stage, with several possible paths across stages other than the first and the last.
Self-routing data internal to the node is associated with each cell by translator means at the node input. The translator means deduce the internal routing data from the external routing data: virtual circuit identity and virtual circuit group identity. If a cell is addressed to a group of outputs, the internal routing data designates all of the destination group of the cell. Thus it does not identify the specific output to be finally selected dynamically by the switching node to transfer the cell in question to the destination group.
The switching network employed is capable of group routing. Each switching element identifies a group of outputs from among its own outputs on the basis of internal self-routing data associated with the cell. The outputs so identified are those providing access to the output (or to the group of outputs) of the network and thus to the output (or to the group of outputs) of the node constituting the destination of the cell. A group of outputs of a switching element providing access to an output (or to a group of outputs) of the node is called a routing group.
The switching element then selects any output from the so identified routing group outputs at random and transfers the cell to this selected output.
The method for identifying the routing group in a switching element is as follows: a cell to be transferred to a given destination includes a destination address in its internal self-routing data. Consider, for example, a cell to be transferred from an input of the node to any output of a group of eight outputs of the node whose addresses are given by the mathematical relationship 1792+k*32 where k=1, 2, 3, . . . , 8 and where "*" is the multiplier sign. The self-routing group address of a cell comprises three bit fields: 11, XXX, 11111. These three bit fields can, for example, correspond to the routing data successively used by the switching elements of a three-stage switching network.
A switching element of the first stage receives the cell and analyzes the first field of the label: the value "11" of the first field identifies one output (or one group of outputs) from four outputs (or from four groups of outputs) of this first stage switching element. The cell is transferred to this output or to one of the outputs of the routing group.
The second switching element analyzes the second field: the value "XXX" of the second field simultaneously identifies all the eight outputs of this switching element. The switching element selects any one of these outputs at random, in such a way as to achieve as regular a statistical distribution as possible, in the short term, as the network has a regular structure in this example. The cell is transferred to the selected output.
The last switching element analyzes the third value: the value "11111" identifies a single one of the 32 outputs of the switching element. This output is connected to an output of the network. All outputs of a second stage switching element are uniformly distributed to the various switching elements of the third stage. Consequently, the distribution effected by the second stage elements distributes successive cells having the same group destination address 11 XXX 11111 to eight outputs of the switching network having addresses related by the expression 1792+k*32. If the distribution is random in the short term the cells are regularly distributed to the eight outputs of the node belonging to the destination regular group.
To implement a switching network of this kind it is possible to use switching elements as described in French patent application FR-A-2 659 819. This switching element is capable of routing cells to groups of outputs (routing groups), statistically balancing the load between the outputs of a group of outputs of the switching element. Selection is effected either by means of a pseudo-random signal generator or on the basis of the respective contents of the outputs queues of the switching element concerned. This known switching element can therefore distribute cells regularly to a regular group of outputs of the node. However, it has the drawback of enabling distribution of cells only when the groups of outputs are regular. The regular groups rule out the use of wild card bit values to identify outputs of a switching element.
An object of the invention is therefore to propose a switching node enabling distribution of cells, cell by cell, to the various links of a group of external links, even when this group is irregular. The solution achieving this object must additionally be compatible with the various conventional methods of routing a cell to a single link. Another object of the invention is to enable distribution of cells in the case of a point-to-multipoint transfer, each destination being an individual link or a group of links.
A trivial solution would be to use the switching network of a node twice in succession for each cell:
A solution of this kind entails doubling the capacity of the switching network and consequently is not practicable except for a very small network indeed.